1. Field of the Invention
The present invention relates to an M-sequence generator, a providing method thereof, and a random error generating device in which the M-sequence generator is used, particularly to a random error generating device that has a specified error rate and supplies a random error signal whose error distribution approximates an error distribution caused by a noise generated in optical communication and electric communication, an M-sequence generator that can be applied to the random error generating device, and a method for providing the M-sequence generator.
2. Description of the Related Art
Generally, in a test apparatus that performs various tests to various communication instruments incorporated in a digital communication network in which an electric signal cable is used or an optical communication network in which an optical fiber cable is used, a test signal matched with actual usage of the communication instrument of a test target is fed into the communication instrument to evaluate a reply operation of the communication instrument.
In one of kinds of evaluation tests of the communication instrument, a test signal intentionally including an error matched with the actual usage is adopted as a test signal fed to the communication instrument of a measurement target.
It is evaluated that the communication instrument is normally operated to what extent of an incidence rate (error rate) E of an error included in the test signal.
For example, Patent Document 1 proposes a random error generating device in which the error is randomly included in the test signal.
Although a detailed configuration of the random error generating device is not clearly described in Patent Document 1, it can be assumed that the random error generating device has the configuration of FIGS. 15 and 16 from the specification and the drawings.
As illustrated in FIG. 16, an example of an M (Maximum length periodic)-sequence generator 1 comprises a series-connected m-stage registers 2 and one or plural EXCLUSIVE-OR gates 3.
When an external clock circuit 4 applies a clock (CLK) to each register 2, a PN (Pseudo Noise) signal that is of a digital series signal having a period of (2m-1) is supplied from an output terminal 5.
Pieces of bit data stored in m registers 2 are supplied in parallel in each time the clock (CLK) is fed.
The pieces of bit data supplied in parallel from the M-sequence generator 1 are applied to one (X terminal) of input terminals of a comparator 6.
A parallel m-bit reference value that an operator inputs with a reference value setting circuit 7 is fed into the other input terminal (Y terminal) of the comparator 6.
The comparator 6 takes in the parallel m pieces of bit data applied to one (X terminal) of the input terminals as one numerical value A while taking in the parallel m-bit reference value B applied to the other input terminal (Y terminal) also as one numerical value.
When the numerical value A taken in from one (X terminal) of the input terminals is equal to or lower than the reference value B taken in from the other input terminal (Y terminal), the comparator 6 supplies a random error signal a that becomes an error bit.
The reference value B is set according to an error incidence rate (error rate) E of the random error signal a supplied from the random error generating device.
For example, the reference value B is set to “4”, when the error rate E is 0.004 (0.4%) and the numerical value A at the X terminal ranges from 1 to 1000.
At this point, the random error signal a having the error rate E of 0.004 is obtained because a probability that the numerical value A is equal to or less than 4 become 4/1000.    Patent Document 1: Jpn. Pat. Appln. KOKAI Publication No. 2002-330192
However, even in the random error generating device of FIGS. 15 and 16, there are following problems to be solved.
For example, in the M-sequence generator 1 of FIG. 15 in which series-connected m registers 2 are incorporated, a sequence of pieces of data that are supplied sequentially from the output terminal 5 in synchronization with the clock from the M-sequence generator 1 changes from the number of installed EXCLUSIVE-OR gates 3 and an installation position.
A period indicating a repetition of the same data stream also changes in the supplied sequence (data stream).
There are plural sequences in which the maximum length periodic sequences (2m-1) are obtained.
That is, as is well known, the M (maximum length periodic) sequence is expressed by the following periodic sequence in which all the elements except a zero element “0” in a two-element Galois extension Field (2m) is obtained by the powers of primitive elements α.
α0, α1, α2, α3,
As used herein, the primitive element α means a special element in which all the elements except the zero element “0” of a Galois field GF(pm) is produced by the power of α.
A Galois field that is obtained by extending a Galois prime field GF(p) is referred to as a Galois extension field GF(pm). Where p is a prime number and m is a positive integer which is 2 or more. The Galois prime field GF(p) is referred to as a basic field of the Galois extension field GF(pm).
A polynomial in which an element of the Galois basic field GF(p) is used as a coefficient is referred to as a “polynomial on the Galois basic field GF(p)”.
When the Galois basic field GF(p) is GF(2), because of the element [0,1], the polynomial has is expressed by the following m-order polynomial in which the elements (b0, b1, b2, b3, . . . , and bm) of the Galois basic field GF(2) are used as the coefficient:q(x)=bmxm+bm-1xm-1+, . . . , +b1x+b0 Accordingly, there are (2m+1) polynomials.
The root of the m-order polynomial q(x) on the Galois basic field GF(2) is x satisfying q(x)=0.
When the polynomial q(x) does not have the root that is the element of the Galois basic field GF(p), it is said that the polynomial q(x) is irreducible on the Galois basic field GF(p).
It is also said that the polynomial q(x) is an irreducible polynomial on the Galois basic field GF(p).
For example, when the Galois basic field GF(p) is GF(2), a polynomial q(x)=x3+x+1 is the irreducible polynomial on the Galois basic field GF(p).
This can easily be confirmed by substituting “0” and “1” that are of the elements of the Galois basic field GF(2) for the polynomial q(x).
For example, when x=0 and x=1 are substituted for the polynomial q(x)=x3+x+1,q(0)=03+0+1≠0, andq(1)=13+1÷1=1≠0are obtained. Therefore, the root of the polynomial q(x) is neither “0” nor “1”.
Accordingly, the polynomial q(x) is the irreducible polynomial on the Galois field GF(2).
The polynomial having the maximum length periodic sequence (2m-1) in the irreducible polynomials is defined as a primitive polynomial p(x).
It can easily be proved that the polynomial is the irreducible polynomial p(x) when the number of terms of the polynomial is an odd number.
As illustrated in FIGS. 9 and 10, when the number of orders m increases, there are plural primitive polynomials (primitive polynomial) p(x) in which the maximum length periodic sequences (2m-1) are obtained.
The element that is of the root of the primitive polynomial p(x) becomes the primitive element α.
However, in the conventional M-sequence generator 1, frequently the primitive polynomial p(x) having the minimum number of terms (trinomial or pentanomial) is adopted in order to simplify a circuit configuration.
In the M-sequence generator 1 of FIG. 16, the adopted primitive polynomial p(x) is formed by a trinomial.p(x)=x10+x3+1
Usually the primitive polynomial described in specialized books and literatures is frequently a trinomial or a pentanomial.
However, a probability distribution of a pseudo-random number produced by the M-sequence generator 1 differs largely from a generation probability distribution of the naturally generated noise, and there are following points (a), (b), and (c) that should be improved as a characteristic of the M-sequence generator.
(a) In the M-sequence generator 1 formed by the shift registers, a probability that contents of the shift register become only original contents shifted right or left by one bit with respect to the input of one clock (CLK). Therefore, when the error bit is generated, there is a high possibility that the same error bit is continued over the plural clocks.
Particularly the problem is easily generated when the primitive polynomial p(x) having a small number of terms is selected as the generating polynomial.
For example, FIG. 10 illustrates examples of the primitive polynomials p(x) of order (stage number) m=3 to order m=32, which are adopted in the conventional M-sequence generator 1.
The primitive polynomial p(x) in each order m of FIG. 10 is the primitive polynomial p(x) having the minimum number of terms in the plural primitive polynomials p(x) of the corresponding order m of FIG. 9.
The primitive polynomial p(x) in which the minimum number of terms is an odd number is the trinomial as illustrated in FIG. 10, the primitive polynomial p(x) of the trinomial does not always exist with respect to any order (stage number) m.
For example, for the order (stage number) m=8, the primitive polynomial p(x) having the minimum number of terms is the following pentanomial.p(x)=x8+x7+x2+x+1
At least the primitive polynomial p(x) having the minimum number of terms is selected.
When the number of terms of the adopted primitive polynomial p(x) decreases, the number of pieces of bit data decreases in the M-sequence generator 1 of FIG. 16, wherein the number of pieces of bit data is fed back from the subsequent registers 2 to the leading register 2 through the EXCLUSIVE-OR gate 3.
As a result, there is a probability that the same value of “1” or “0” is continued in the bit data string of the maximum length periodic sequence (2m-1) sequentially supplied from the M-sequence generator 1 in synchronization with the clock (CLK).
Accordingly, the further randomized error distribution that is of the target is not obtained in the M-sequence generator 1.
(b) In the M (maximum length periodic)-sequence generator 1, the probability distribution of the pseudo-random number produced by the M (maximum length periodic)-sequence generator 1 cannot be brought close to the generation probability distribution of the naturally generated noise only by increasing the order (stage number) m, that is, lengthening the period.
It is necessary that the period of the maximum length periodic sequence be lengthened in order to improve the probability distribution characteristic.
However, when the period is more than a certain value, a contribution ratio of the lengthened period is reduced to the improvement of the generation probability distribution characteristic.
For example, the period of (2127-1), that is, the periodic sequence of about 1.7×1038 is obtained in the M-sequence generator 1 in which the 127-stage (m=127) shift register is used.
In fact, the period of about 1.7×1038 is equal to an infinite length.
However, in the actual test measurement, there is a need for the excellent probability distribution characteristic in a relatively short test time.
It is clear that only lengthening the period of the periodic sequence cannot deal with the need.
In the M-sequence generator 1 and random error generating device, advantageously the circuit scale can be minimized, and the high-speed operation can be performed. At the same time, there still is a room for improvement in the probability distribution characteristic and probability process characteristic of the supplied random error signal.
(c) In the M-sequence generator 1 of FIG. 16, when the M-sequence generator 1 is realized on an application program of a computer, each pieces of data fed into and supplied from each register 2 is obtained by the Galois field multiplication including the primitive polynomial p(x).
However, in such cases, the Galois field multiplication cannot be realized only by one clock (CLK) supplied from the clock circuit 4.
That is, as illustrated in FIG. 16, in the M-sequence generator 1 comprising the 10-stage (order m=10) shift register 2, because each register 2 takes in data of the preceding-stage register 2 in response to the clock, the Galois field multiplication of the primitive polynomial p(x)=x10+x3+1 of the trinomial in the order m=10 of FIG. 10 is not completed only by one clock (CLK) supplied from the clock circuit 4.
10 clocks (CLK) for the order m (=10) of the registers 2 are required in FIG. 16.
Accordingly, the high-speed performance is degraded in the random error generating device comprising the M-sequence generator 1 of FIG. 16.